'''
https://leetcode.cn/problems/maximum-average-subarray-ii
'''
from typing import List


class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        def check(avg):
            end_sum = sum(num - avg for num in nums[:k])
            start_sum = min_start_sum = 0
            for end in range(k, len(nums)):
                if end_sum >= min_start_sum:
                    return True
                end_sum += nums[end] - avg
                start_sum += nums[end - k] - avg
                min_start_sum = min(start_sum, min_start_sum)
            return end_sum >= min_start_sum

        l, r = min(nums), max(nums)
        while r - l > 1e-5:
            mid = (l + r) / 2
            if check(mid):
                l = mid
            else:
                r = mid
        return r

    # 暴力
    def findMaxAverage2(self, nums: List[int], k: int) -> float:
        n = len(nums)
        pre_sum = [0] * (n + 1)
        for i in range(n + 1):
            pre_sum[i] = pre_sum[i - 1] + nums[i - 1]

        res = float('-inf')
        for k in range(k, n + 1):
            for i in range(k, n + 1):
                res = max(res, (pre_sum[i] - pre_sum[i - k]) / k)
        return res
